/*
 * @lc app=leetcode.cn id=332 lang=java
 *
 * [332] 重新安排行程
 */

// @lc code=start
import java.util.*;;
class Solution {
    int total;
    public List<String> findItinerary(List<List<String>> tickets) {
        total = tickets.size() + 1;
        // 遍历ticket存入map
        for(List<String> ticket : tickets) {
            addNew(ticket.get(0), ticket.get(1));
        }

        deal("JFK");
        return res;
    }

    Map<String, LinkedList<String>> map = new HashMap<>();
    List<String> res = new LinkedList<>();
    private boolean deal(String currentLocation) {
        res.add(currentLocation);

        if(res.size() == total) {
            return true;
        }

        // 当前位置的终点列表
        List<String> targetLocations = map.get(currentLocation);
        // 如果没有从当前位置出发的机票了，说明这条路走不通
        if(targetLocations != null && !targetLocations.isEmpty()) {
            String targetLocation;
            for(int i = 0; i < targetLocations.size(); i++) {
                if(i > 0 && targetLocations.get(i).equals(targetLocations.get(i-1))) {
                    continue;
                }

                targetLocation = targetLocations.get(i);
                targetLocations.remove(i);

                if(deal(targetLocation)) {
                    return true;
                }

                targetLocations.add(i, targetLocation);
                res.removeLast();
            }
        }
        return false;
    }

    // 按照字典顺序添加元素
    private void addNew(String start, String end) {
        LinkedList<String> startALLend = map.getOrDefault(start, new LinkedList<>());
        if(!startALLend.isEmpty()) {
            for(int i = 0; i < startALLend.size(); i++) {
                if(end.compareTo(startALLend.get(i)) < 0) {
                    startALLend.add(i, end);
                    return;
                }
            }
            startALLend.add(startALLend.size(), end);
        } else {
            startALLend.add(end);
            map.put(start, startALLend);
        }
    }
}
// @lc code=end

